[APIO2016]划艇

2020-01-22
#组合数学 #动态规划Dp #离散化
APIO

题意

有n个数，每个数可以在$[a_i,b_i]$之间取值，也可以取0

要求数列中所有非零数构成严格递增序列

求方案数

题解

容易想到用$f_{i,max}$表示dp完前i个之后最大值为max的方案数

由于a、b太大，而我们关心的只是大小关系，因此想到离散化，令$f_{i,j}​$表示dp完前i个之后最大值在离散后的第j个区间中

$f_{i,j}$由两部分得到：当p<j，$\sum_{p=0}^{j-1} f_{i-1,p} \cdot (t_{j+1}-t_j)$

当p=j，我们发现还须知道前面的数中有几个在该区间内，那么再加入一维状态k，

一个trick：离散化的时候把$a_i$和$b_i+1$丢进去，这样区间就是左闭右开的了

调试记录

一开始没有考虑p=j的情况

线性逆元打错了

f开小了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <algorithm>
#define int long long
const int maxn = 505;
const int mo = 1e9 + 7;
using namespace std;
int a[maxn], b[maxn], f[maxn << 1][maxn], sum[maxn << 1], lim[maxn << 1];
int n, ans = 0, tmp[maxn << 1], inv[maxn << 1]; // f [)
signed main(){
//	freopen("1.in", "r", stdin);
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lld%lld", a + i, b + i);
		tmp[i * 2 - 1] = a[i]; tmp[i * 2] = b[i] + 1;
	} sort(tmp + 1, tmp + 2 * n + 1);
	int cnt = unique(tmp + 1, tmp + 2 * n + 1) - tmp - 1;
	for (int i = 1; i <= n; i++){
		a[i] = lower_bound(tmp + 1, tmp + cnt + 1, a[i]) - tmp;
		b[i] = lower_bound(tmp + 1, tmp + cnt + 1, b[i] + 1) - tmp;
	}
	inv[1] = 1;
	for (int i = 2; i <= n * 2; i++) inv[i] = 1ll * inv[mo % i] * (mo - mo / i) % mo;
	f[0][0] = 1;
	for (int j = 0; j < cnt; j++) sum[j] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = a[i]; j < b[i]; j++){
			++lim[j];
			for (int k = lim[j] - 1; k >= 1; k--)
				f[j][k + 1] = (f[j][k + 1] + 1ll * f[j][k] * (tmp[j + 1] - tmp[j] - k) % mo * inv[k + 1] % mo) % mo;
			f[j][1] = (f[j][1] + 1ll * sum[j - 1] * (tmp[j + 1] - tmp[j]) % mo) % mo;
		}
		for (int j = 1; j < cnt; j++){
			sum[j] = sum[j - 1];
			for (int k = lim[j]; k >= 0; k--) sum[j] = (sum[j] + f[j][k]) % mo;
		}
	}
	printf("%lld\n", (sum[cnt - 1] - 1 + mo) % mo);
	return 0;
}